Leetcode 二叉树

104 二叉树最大深度

xxxxxxxxxx
class Solution {
    public int maxDepth(TreeNode root) {
        return root == null? 0: 1+Math.max(maxDepth(root.left), maxDepth(root.right));
    }
}

110 平衡二叉树

递归计算左右子树深度，-1 是计算错误退出标志，这种处理方式是比较好的。

​x
class Solution {
    public boolean isBalanced(TreeNode root) {
        return getDepth(root) >= 0;
    }
​
    public int getDepth(TreeNode root) {
        if(root == null) {
            return 0;
        }
        int left = getDepth(root.left);
        int right = getDepth(root.right);
        if(left<0 || right<0 || Math.abs(left-right) >1) {
            return -1;
        } else {
            return Math.max(left, right)+1;
        }
    }
}

236 二叉树的最近公共祖先

若左右子树均找到目标，返回根节点，否则返回左或右结点。

xxxxxxxxxx
class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null || root == p || root == q) {
            return root;
        }
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        if(left != null && right != null) {
            return root;
        } else if (left != null) {
            return left;
        } else if (right != null) {
            return right;
        }
        return null;
    }
}

102 二叉树层次遍历

此题要求输出每层的情况，除了使用队列外，应注意使用两层循环结构逐层输出。

xxxxxxxxxx
class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> res = new LinkedList<List<Integer>>();
        LinkedList<TreeNode> deq = new LinkedList<>();
        if(root == null) {
            return res;
        }
        deq.offer(root);
        while(! deq.isEmpty()) {
            int count = deq.size();
            LinkedList<Integer> tmp = new LinkedList<>();
            for(int i=0; i<count; i++) {
                TreeNode node = deq.removeFirst();
                tmp.add(node.val);
                if(node.left != null) {
                    deq.offer(node.left);
                }
                if(node.right != null) {
                    deq.offer(node.right);
                }
            }
            res.add(new ArrayList<Integer>(tmp));
        }
        return res;
    }
}

103 二叉树层次遍历倒序

每次把部分结果往队头放，或者用栈暂存。

xxxxxxxxxx
class Solution {
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        LinkedList<List<Integer>> res = new LinkedList<List<Integer>>();
        LinkedList<TreeNode> deq = new LinkedList<>();
        if(root == null) {
            return res;
        }
        deq.offer(root);
        while(! deq.isEmpty()) {
            int count = deq.size();
            LinkedList<Integer> tmp = new LinkedList<Integer>();
            for(int i=0; i<count; i++) {
                TreeNode node = deq.removeFirst();
                tmp.add(node.val);
                if(node.left != null) {
                    deq.offer(node.left);
                }
                if(node.right != null) {
                    deq.offer(node.right);
                }
            }
            res.addFirst(tmp);
        }
        return res;
    }
}

98 验证二叉搜索树

二叉搜索树的左子树的值小于root，右子树的值大于root，因此中序遍历是升序。

class Solution {
    private double last = -Double.MAX_VALUE;
    public boolean isValidBST(TreeNode root) {
        if(root == null) {
            return true;
        }
        boolean left = isValidBST(root.left);
        if(left == false) {
            return false;
        }
        if(last < root.val) {
            last = root.val;
        } else {
            return false;
        }
        boolean right = isValidBST(root.right);
        if(right == false) {
            return false;
        }
        return true;
    }
}